#include <iostream>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <climits>
#include <sys/time.h>
#include <math.h>

#include <set>
#include <queue>
#include <string>

using namespace std;

//test for binary search tree
//left<=parent<=right
struct Node{
        Node* parent;
        Node* left;
        Node* right;
        
        int val;
        bool blocked;//false means unblocked
        bool lff, rfl;//true means unblocked
        pthread_cond_t cond;
        pthread_mutex_t lock;//Open for any operation
        Node (Node* m_parent = NULL, Node* m_left = NULL, Node* m_right = NULL, int m_val = INT_MIN, 
              bool m_blocked = false, bool m_lff = true, bool m_rfl = true) 
        : parent(m_parent), left(m_left), right(m_right), val(m_val), blocked(m_blocked),
                lff(m_lff), rfl(m_rfl) {pthread_cond_init(&cond, NULL); pthread_mutex_init(&lock, NULL);}
};


enum OP{
        INSERT,
        SEARCH,
        REMOVE,
        NA
};


struct workArg{
        OP func;
        int val;
        void* classPointer;
        workArg (OP m_func = NA, int m_val = -1, void* m_classPointer = NULL) 
        : func(m_func), val(m_val), classPointer(m_classPointer) {}
};


struct retArg{
        OP func;
        int val;
        bool status;
        Node* node;
        retArg (OP m_func = NA, int m_val = -1, bool m_status = false, Node* m_node = NULL) 
        : func(m_func), val(m_val), status(m_status), node(m_node){}
};


class MyThreadClass
{
  public:
        MyThreadClass() {/* empty */}
        ~MyThreadClass() {/* empty */}
        
        bool initThreads(unsigned int thread_num){
                thread_num = thread_num;
                threads = new pthread_t [thread_num];
        }
        
        void destroyThreads(void){
                delete [] threads;
        }
        
        /** Returns true if the thread was successfully started, false if
         * there was an error starting the thread */
        bool createThread(unsigned int tid, workArg* wa)
        {
                int ret = 0;
                if(wa->func == INSERT)
                        ret = ret | (pthread_create(&threads[tid], NULL, runInsertwrapper, (void*)wa));
                else if(wa->func == SEARCH)
                        ret = ret | (pthread_create(&threads[tid], NULL, runSearchwrapper, (void*)wa));
                else if(wa->func == REMOVE)
                        ret = ret | (pthread_create(&threads[tid], NULL, runRemovewrapper, (void*)wa));
                else{
                        cout << "Function is not supported for multithreading." << endl;
                        return false;
                }
                return (ret == 0);
        }
        
        //Keep in mind, if you want to change the address value of a
        //pointer, you have to either use ** or reference to pointer
        void joinThreads(unsigned int tid, retArg* &rt){//retArg*& !!!
                pthread_join(threads[tid], (void**)&rt);
                //cout << "Operation is " << rt->func << endl;
        }
        
  protected:
        /** Implement this method in your subclass with the code you want
         * your thread to run. */
        virtual void* runInsert(int) = 0;
        virtual void* runSearch(int) = 0;
        virtual void* runRemove(int) = 0;

  private:
        //These are for the pthread work function, has to be static to
        //remove the (*this) when passing to pthread
        static void * runSearchwrapper(void * This) {
                return ((MyThreadClass *)((workArg*)This)->classPointer)->runSearch(((workArg*)This)->val);
        }
        
        static void * runInsertwrapper(void * This) {
                return ((MyThreadClass *)((workArg*)This)->classPointer)->runInsert(((workArg*)This)->val);
        }
        
        static void * runRemovewrapper(void * This) {
                return ((MyThreadClass *)((workArg*)This)->classPointer)->runRemove(((workArg*)This)->val);
        }
        
        unsigned int thread_num;
        pthread_t* threads;//Make sure all threads are used
};


class bstree : public MyThreadClass {
  public: 
  bstree(Node* m_root = NULL) : root(m_root)
        {pthread_mutex_init(&lock, NULL); pthread_cond_init(&cond, NULL);} 
        ~bstree(){destroy();}
        
        void destroy();
        void print();
        
        Node* find_min(Node* psuedo_root);
        Node* find_max(Node* psuedo_root);
        
        virtual void* runInsert(int);
        virtual void* runRemove(int);
        virtual void* runSearch(int);
        
        void* insert(int);
        Node* search(int);
        bool remove(int val);
        
  private:
        bool remove(Node*);
        void* insert(int val, Node* leaf);
        Node* search(int val, Node* leaf);
        //bool remove(int val, Node* leaf);
        void destroy(Node* leaf);
        pthread_cond_t cond;
        pthread_mutex_t lock;
        
        Node* root;
        pthread_t* myThreads;
};
